package com.nav.util;

public class DePriorityQueue<T extends Comparable<T>> {
	private int size = 0;
	private Node<T> r;
	private static class Node<T extends Comparable<T>> {
		Node<T> l, r;
		T v;
		public Node(T v) {
			this.v = v;
		}
	}
	public int size() {
		return size;
	}
	public void add(T v) {
		size++;
		if(r == null) {
			r = new Node<T>(v);
		} else {
			Node<T> c = r;
			while(true) {
				if(v.compareTo(c.v) <= 0) {
					if(c.l == null) {
						c.l = new Node<T>(v);
						return;
					}
					c = c.l;
				} else {
					if(c.r == null) {
						c.r = new Node<T>(v);
						return;
					}
					c = c.r;
				}
			}
		}
	}
	public T pollFirst() {
		if(r == null)
			return null;
		size--;
		if(r.l == null) {
			T ret = r.v;
			r = r.r;
			return ret;
		}
		Node<T> c = r;
		while(c.l.l != null)
			c = c.l;
		T ret = c.l.v;
		c.l = c.l.r;
		return ret;
	}
	public T pollLast() {
		if(r == null)
			return null;
		size--;
		if(r.r == null) {
			T ret = r.v;
			r = r.l;
			return ret;
		}
		Node<T> c = r;
		while(c.r.r != null)
			c = c.r;
		T ret = c.r.v;
		c.r = c.r.l;
		return ret;
	}
}
